1. Field
The present invention relates generally to communications. More particularly, in aspects the invention relates to operation of fast Fourier transform engines.
2. Background
Modern wireless communication systems are widely deployed to provide various types of communication applications, such as voice and data applications. These systems may be multiple access systems capable of supporting communication with multiple users by sharing the available system resources (e.g., spectrum and transmit power). Examples of multiple access systems include code division multiple access (CDMA) systems, time division multiple access (TDMA) systems, frequency division multiple access (FDMA) systems, time division duplexing (TDD) systems, frequency division duplexing (FDD) systems, 3rd generation partnership project long term evolution (3GPP LTE) systems, and orthogonal frequency division multiple access (OFDMA) systems. There are also point-to-point systems, peer-to-peer systems, and wireless local area networks (wireless LANs).
Generally, a wireless multiple access communication system can simultaneously support communications with multiple wireless terminals. Each terminal communicates with one or more base transceiver stations (BTSs or base stations) via transmissions on forward and reverse links. The forward link or downlink refers to the communication link from a base transceiver station to a terminal, and the reverse link or uplink refers to the communication link from a terminal to a base transceiver station. Each of the forward and reverse communication links may be established via a single-in-single-out, multiple-in-single-out, single-in-multiple-out, or a multiple-in-multiple-out (MIMO) communication technique, depending on the number of transmitting and receiving antennae used for the particular link.
MIMO systems are of particular interest because of their relatively higher data rates, relatively longer coverage range, and relatively more reliable transmission of data. A MIMO system employs multiple (NT) transmit antennae and multiple (NR) receive antennae for data communication. A MIMO channel formed by the NT transmit and NR receive antennae may be decomposed into NS independent channels, which are also referred to as spatial channels, where NS≦min{NT, NR}. Each of the NS independent channels corresponds to a dimension. The MIMO system can provide improved performance (e.g. higher throughput and/or greater reliability) if the additional dimensions created by the multiple transmit and receive antennae are used.
Communication systems often perform at least some processing of the received signals in the frequency domain. The received signals are typically transformed from time domain to the frequency domain using Fourier transforms. Conversely, inverse Fourier transforms can be used to transform frequency domain signals to the signals' time domain counterparts. Additionally, communication systems, such as those implementing Orthogonal Frequency Division Multiplexing (OFDM), can use certain properties of Fourier transforms to generate multiple time domain symbols from linearly spaced tones and to recover the frequencies from the symbols.
Fast Fourier Transform (FFT) is a computational algorithm implementing the Fourier transform. The FFT allows the Fourier transform to be performed in fewer computational operations than used for discrete Fourier transform (DFT). Often, the module responsible for the FFT (the “FFT engine”) in a wireless device is implemented as a sequence of “butterflies.” A “butterfly” in this context is a computational portion of the FFT engine that implements a small (relative to the entire FFT engine) DFT. The term “butterfly” typically appears in description of the Cooley-Tukey FFT algorithm. The Cooley-Turkey algorithm breaks down a DFT of composite size n=(r·m) into r smaller transforms of size m, where r is the so-called “radix” of the FFT transform. The breakdown is performed recursively, and the smaller transforms are combined with size-r butterflies, which themselves are DFTs of size r (performed m times on the outputs of the smaller transforms) pre-multiplied by roots of unity. The steps can also be performed in reverse, so that the butterflies come first and are post-multiplied by the roots of unity.
The output of the FFT engine is usually stored on a processing chip in an output buffer or Random Access Memory (RAM), for further processing in the frequency domain. The size of the output buffer can be quite large, and occupy a significant percentage of the application-specific integrated circuit (ASIC), increasing die-area and cost. For example, a wireless standard may define a Packet or Frame to have eight OFDM symbols, each with 1024 tones. In such a case, the mobile device with four receive antennae may have to instantiate an output buffer that needs to store eight OFDM symbols times 1024 tones times four receive antennas times 16 bit I/Q samples, resulting in a one Mbit buffer. With double-buffering of output Frames, the size increases to two Mbits.
The input time domain signal may fluctuate significantly. For example, every OFDM symbol can have a different power level and different spectral characteristics. This is because of the power control, adaptive or otherwise, and the varying nature of the physical channel, which is subject to noise, multipath and fading, attenuation, Doppler shift, and interference. The significant fluctuations of the signal amplitude at the FFT output—i.e., increased dynamic range—necessitate additional increases in the memory used for buffering the output of the FFT engine of a wireless device.
Because memory is a scarce resource—with weight, size, and power consumption costs in addition to the direct economic cost—a need exists in the art for apparatus, methods, and articles of manufacture that reduce the buffer size requirement at the output of the FFT engine. Another need exists in the art to reduce FFT engine output buffer requirement without compromising other performance characteristics, including dynamic range. Yet another need exists to reduce the computational resources used by the butterflies in the FFT engine.